package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/
 * @create 2025/9/29 19:36
 * @since JDK17
 */

public class Solution92 {
    static int N = ((int) (1e5 + 10));
    static int[] size = new int[N], dfn = new int[N], deep = new int[N], maxr = new int[N], maxl = new int[N];
    int dfnCnt;
    void dfs(TreeNode root, int k) {
        int i = ++dfnCnt;
        dfn[root.val] = i;
        size[i] = 1;
        deep[i] = k;
        if (root.left != null) {
            dfs(root.left, k + 1);
            size[i] += size[dfn[root.left.val]];
        }
        if (root.right != null) {
            dfs(root.right, k + 1);
            size[i] += size[dfn[root.right.val]];
        }
    }

    public int[] treeQueries(TreeNode root, int[] queries) {
        int m = queries.length;
        int[] ans = new int[m];
        dfs(root, 0);
        for (int i = 1; i <= dfnCnt; i++) {
            maxl[i] = Math.max(maxl[i - 1], deep[i]);
        }
        for (int i = dfnCnt; i > 0; i--) {
            maxr[i] = Math.max(maxr[i + 1], deep[i]);
        }
        for (int i = 0; i < m; i++) {
            ans[i] = Math.max(maxl[dfn[queries[i]] - 1], maxr[dfn[queries[i]] + size[dfn[queries[i]]]]);
        }

        return ans;
    }
}
